package week_seven;

public class RedundantConnectionDisjointSet_684 {
    //并查集解法
    int[] fa;

    public int[] findRedundantConnection(int[][] edges) {
        //n个顶点
        int n = 0;
        for (int[] edge : edges) {
            n = Math.max(n, edge[1]);
        }

        fa = new int[n + 1];
        for (int i = 0; i <= n; i++) fa[i] = i;

        for (int[] edge : edges) {
            int x = edge[0];
            int y = edge[1];
            if (find(x) == find(y)) return edge;
            else union(y, x);
        }
        return null;

    }

    private int find(int x) {
        if (x == fa[x]) return x;
        return fa[x] = find(fa[x]);
    }

    private void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) fa[x] = y;
    }
}
